package 牛客.动态规划;

public class BM72连续子数组的最大和 {
    public int FindGreatestSumOfSubArray(int[] array) {
        //暴力在牛客超时
        int max=array[0];
        int sum=0;
        for (int i = 0; i <array.length; i++) {
            sum=0;
            for (int j = i; j <array.length; j++) {
                sum += array[j];
                max=Math.max(sum,max);
            }
        }
        return max;
    }

    public int FindGreatestSumOfSubArray1(int[] array) {
        int maxSum=Integer.MIN_VALUE;
        int curSum=0;

        for (int i = 0; i <array.length; i++) {
            if (curSum+array[i]>0) {
                curSum += array[i];
            }else {
                curSum=0;
            }

            if (curSum>maxSum) {
                maxSum=curSum;
            }
        }

        if (maxSum==0) {
            //数组中没有大于0的数
            for (int i = 0; i <array.length; i++) {
                if(i==0) {
                    maxSum=array[i];
                }
                if (array[i] > maxSum) {
                    maxSum=array[i];
                }
            }
        }
        return maxSum;

    }
}
